package algo.A03_递归和算法复杂度;

/**
 * 有个排序后的字符串数组，其中散布着一些空字符串，编写一个方法找出给定字符串(肯定不是空字符串)的位置。
 */
public class T12_在有空字符串的有序字符串数组中查找_二分法 {
    public static void main(String[] args) {
        String[] arr = {"a", "", "ac", "", "ad", "b", "", "ba"};
        int result = solution(arr, "abc");
        System.out.println("result = " + result);
    }

    private static int solution(String[] arr,String target) {
        int begin = 0;
        int end = arr.length - 1;
        //当begin和end相邻时结束循环
        while (begin + 1 < end){
            int mid = begin + (end - begin) / 2;
            //当arr[mid]为空时mid要左右移动
            while ("".equals(arr[mid])){
                mid++;
            }
            //目标比中间值大，在右边找
            if (target.compareTo(arr[mid]) > 0){
                begin = mid + 1;
            }else if (target.compareTo(arr[mid]) < 0){//目标比中间值小，在左边找
                end = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }
}
